import java.util.LinkedList;
import java.util.List;
import java.util.Stack;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-11-20
 * Time:0:02
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
class Solution {
        public boolean isCompare(TreeNode left,TreeNode right){
            if(left==null&&right==null){
                return true;
            }
            if(left!=null&&right!=null&&left.val==right.val){
                return isCompare(left.left,right.right)&&isCompare(left.right,right.left);
            }
            return false;
        }
        public boolean isSymmetric(TreeNode root) {
            if(root==null){
                return true;
            }
            return isCompare(root.left,root.right);
        }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int right=height(root.right);
        int left=height(root.left);
        int max=right>left?right:left;
        int min=right>left?left:right;
        if(max-min<2){
            return isBalanced(root.left)&&isBalanced(root.right);
        }else{
            return false;
        }
    }
    public int height(TreeNode root){
        if(root==null){
            return 0;
        }
        int right=height(root.right);
        int left=height(root.left);
        return right>left?right+1:left+1;
    }
    List<Integer> list=new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode prev=null;
        if(root==null){
            return list;
        }
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            TreeNode cur=stack.peek();
            if(cur.right==null||cur.right==prev){
                list.add(stack.pop().val);
                prev=cur;
            }
            else{
                root=stack.peek().right;
            }
        }
        return list;
    }
}

public class Test {
    public static Stack<TreeNode> stack=new Stack<>();
    public static boolean  isSymmetric(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null)){
            return true;
        }
        if(root.left==null||root.right==null){
            return false;
        }
        if(root.left.val==root.right.val){
            stack.push(root.left);
            stack.push(root.right);
        }else{
            return false;
        }
        while(!stack.isEmpty()){
            TreeNode left=stack.pop();
            TreeNode right=stack.pop();
            if(left.left!=null&&right.right!=null&&left.left.val==right.right.val){
                stack.push(left.left);
                stack.push(right.right);
            }else{
                if(left.left==null&&right.right==null){
                }else{
                    return false;
                }
            }
            if(left.right!=null&&right.left!=null&&left.right.val==right.left.val){
                stack.push(left.right);
                stack.push(right.left);
            }else{
                if(left.right==null&&right.left==null){
                }else{
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode treeNode1=new TreeNode(2);
        TreeNode treeNode2=new TreeNode(3);
        TreeNode treeNode3=new TreeNode(3);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(5);
        TreeNode treeNode6=new TreeNode(5);
        TreeNode treeNode7=new TreeNode(4);
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;
        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;
        TreeNode treeNode8=new TreeNode(8);
        TreeNode treeNode9=new TreeNode(9);
        TreeNode treeNode10=new TreeNode(9);
        TreeNode treeNode11=new TreeNode(8);
        treeNode5.left=treeNode8;
        treeNode5.right=treeNode9;
        treeNode7.left=treeNode10;
        treeNode7.right=treeNode11;
        isSymmetric(treeNode1);
        System.out.println();
    }
}
